#ifndef GAMEENGINE_MAPS_HEX_MAP_H
#define GAMEENGINE_MAPS_HEX_MAP_H

#include <GameEngine/Maps/maps_settings.h>

#include <GameEngine/Maps/map.h>

#include <QtCore/QFlags>

#include <list>
#include <vector>



#ifdef GAMEENGINE_NAMESPACES
namespace GameEngine {
#endif

template <class C> class MapCell;
class HexMapSearch;
class HexMapSearchHeuristic;

//=================================================================================


//! A map made of hexagonal cells
/*!
 *  The map contains an array of map cells, which allows to find the shortest path in
 *  the map using the HexMapSearch class.
 */
class _Maps_decl HexMap : public Map {
	//! The hexagonal map search class is friend of the hexagonal map class to allow direct data access
	friend class HexMapSearch;
	//! The hexagonal map search heuristic class is friend of the hexagonal map class to allow direct data access
	friend class HexMapSearchHeuristic;

public:
	//! Enumerates the connections allowed between cells
	enum Connection {
		//! Cell is not connected to any other cell
		NoConnection           = 0,
		//! Cell is connected to cell U-1,V
		LeftConnection         = 1,
		//! Cell is connected to cell U+1,V
		RightConnection        = 2,
		//! Cell is connected to cell U,V-1
		UpConnection           = 4,
		//! Cell is connected to cell U,V+1
		DownConnection         = 8,
		//! Cell is connected to cell U+1,V-1 if V is odd, or U-1,V-1 if V is even
		UpDiagonalConnection   = 16,
		//! Cell is connected to cell U+1,V+1 if V is odd, or U-1,V+1 if V is even
		DownDiagonalConnection = 32
	};

	Q_DECLARE_FLAGS(Connectivity,Connection)

public:
	//! Typedef used to handle cells
	typedef MapCell<Connectivity> Cell;

public:
	HexMap(MapSize width, MapSize height);
	virtual ~HexMap();

	bool get_cell_index(CellIndex& index, const Point2d<float>& rhs) const;
	bool get_cell_index(CellIndex& index, MapIndex x, MapIndex y) const;

	bool get_map_indexes(MapIndex& x, MapIndex& y, const Point2d<float>& rhs) const;

	Cell* get_cell(const Point2d<float>& rhs) const;
	Cell* get_cell(MapIndex x, MapIndex y) const;
	Cell* get_cell(CellIndex index) const;

	std::vector< Point2d<float> > get_cell_geometry(MapIndex x, MapIndex y) const;
	std::vector< Point2d<float> > get_cell_geometry(const Point2d<float>& rhs) const;

protected:
	//! List of cells present in the map
	Cell* cells_;
};

//========================================================

//! Allow to search the shortest path in a hexagonal map
/*!
 *  A hexagonal map search defines a structure that allows to find the shortest path in a hexagonal
 *  map, given the set of displacements that are allowed on this map and the types of displacement
 *  that are allowed by the unit.
 */
class _Maps_decl HexMapSearch {

public:
	//! Node definition for compatibility with the path-searching algorithms
	typedef Map::CellIndex Node;
	//! Cost definition for compatibility with the path-searching algorithms
	typedef float Cost;

	HexMapSearch(const HexMap& map, const Displacement::DisplacementTypes& displacement_types);
	virtual ~HexMapSearch();

	// Path searching definitions
	bool get_children(std::list<Node>& children, Node node) const;
	Cost cost(Node parent, Node node) const;

protected:
	//! The hexagonal map that defines the space of research
	const HexMap& map_;

	//! The types of displacement allowed on this map
	const Displacement::DisplacementTypes& displacement_types_;
};

//========================================================

//! Estimate the remaining distance as the euclidean distance between the current and the end nodes of the grid
/*!
 *  This heuristic is meant to be used with the A-star algorithm. See the AStar documentation for
 *  more informations about the use of heuristic in the shortest path research.
 *
 *  This heuristic usually speeds up the research as compared to the default A-star heuristic if the environment
 *  features quite simple obstacles, i.e., the obstacles do not force the unit to go back at some point. In a
 *  maze-like environment, however, the cost of computing this heuristic are too large as compared to the benefits
 *  of favoring most promising cells, and it is more recommended to use another type of heuristic.
 */
class _Maps_decl HexMapSearchHeuristic {

public:
	HexMapSearchHeuristic(const HexMap& map);
	virtual ~HexMapSearchHeuristic();

	HexMapSearch::Cost cost(HexMapSearch::Node start, HexMapSearch::Node end) const;

protected:
	//! The hexagonal map that defines the space of research
	const HexMap& map_;
};

//========================================================

#ifdef GAMEENGINE_NAMESPACES
} // namespace GameEngine
#endif

#endif
